package 剑指offer;

public class 剑指Offer45把数组排成最小的数 {

    public static void main(String[] args) {
        int[] arr = {10,2};
        剑指Offer45把数组排成最小的数 o = new 剑指Offer45把数组排成最小的数();
        System.out.println(o.minNumber(arr));
    }

    //*****************快排方式1********************
    public String minNumber1(int[] nums) {
        String[] str = new String[nums.length];
        for(int i = 0; i < nums.length;i++){
            str[i] = String.valueOf(nums[i]);
        }
        quickSort(str,0,nums.length - 1);
        StringBuilder sb = new StringBuilder();
        for(String i : str){
            sb.append(i);
        }
        return sb.toString();
    }
    public void quickSort(String[] str,int l ,int r){
        if(l >= r) return;
        int i = l, j = r;
        String temp = str[i];
        while(i < j){
            while( (str[j] + str[l]) . compareTo(str[l] + str[j]) >= 0 && i < j) j--;
            while( (str[i] + str[l]) . compareTo(str[l] + str[i]) <= 0 && i < j) i++;
            swap(str,i,j);
        }
        swap(str,i,l);
        quickSort(str,l,i-1);
        quickSort(str,i+1,r);
    }
    void swap(String[] str,int i,int j){
        String tem = str[i];
        str[i] = str[j];
        str[j] = tem;
    }

    //**************快排方式2***********************
    public String minNumber(int[] nums) {
        String[] str = new String[nums.length];
        for(int i = 0; i < nums.length;i++){
            str[i] = String.valueOf(nums[i]);
        }
        quickSort1(str,0,nums.length - 1);
        StringBuilder sb = new StringBuilder();
        for(String i : str){
            sb.append(i);
        }
        return sb.toString();
    }
    void quickSort1(String[] str,int l,int r){
        if(l >= r){
            return;
        }
        int p = help(str,l,r);//开始设置得标志位就为
        quickSort1(str,l,p-1);
        quickSort1(str,p+1,r);

    }
    int help(String[] str,int l ,int r){
        String point = str[l];
        int i = l;//小于str[i] 得元素范围[l+1，j]
        int j = l + 1;//大于str[i]得元素范围[j+1,r)
        for(; i <= r;i++){
            if((str[i] + str[l]).compareTo(str[l] + str[i]) < 0){
                swap(str,j,i);
                j++;
            }
        }
        swap(str,l,j);
        return j;
    }

}
